package tree;

/**
 * 二叉树的排序查找删除
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode i1 = new HeroNode(1,"d");
        HeroNode i2 = new HeroNode(2,"dd");
        HeroNode i3 = new HeroNode(3,"ddd");
        HeroNode i4 = new HeroNode(4,"dddd");
        HeroNode i5 = new HeroNode(5,"ddddd");
        HeroNode i6 = new HeroNode(6,"dddddd");
        HeroNode i7 = new HeroNode(7,"ddddddd");
        i1.setLeft(i2);
        i1.setRight(i3);
        i2.setLeft(i4);
        i2.setRight(i5);
        i3.setLeft(i6);
        i3.setRight(i7);
        BinartTree b = new BinartTree();
        b.setRoot(i1);
        //b.del(2);
        System.out.println("前序排序：");
        b.preOrder();
        System.out.println("中序排序：");
        b.infixOrder();
        System.out.println("后序排序：");
        b.postOrder();
    }
}
class BinartTree{
    private HeroNode root;
    public void setRoot(HeroNode root){
        this.root=root;
    }
    public void del(int no){
        if(root!=null){
            if(root.no==no){
                root=null;
            }else {
                root.del(no);
            }
        }else {
            System.out.println("二叉树无数据");
        }
    }
public void delNode(int no){
        if(root!=null){
            if (root.no==no){
                root=null;
            }else
            root.delNode(no);
        }else {
            System.out.println("erro!!!!!!!!!");
        }
}
    public void preSearch(int no){
        if(this.root!=null){
            System.out.println(root.preSearch(no));
        }else{
            System.out.println("二叉树无值");
        }

    }
    public void infixSearch(int no){
        if(this.root!=null){
            System.out.println(root.infixSearch(no));
        }else{
            System.out.println("erro!!!!!!!!!!!!!!!1");
        }

    }
    public void postSearsh(int no){
        if(root!=null){
            System.out.println(root.postSearch(no));
        }else{
            System.out.println("二叉树无值");
        }
    }
    public void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树无值");
        }
    }
    public void infixOrder(){
        if(this.root!=null){
            this.root.infixOrder();
        }else{
            System.out.println("erro!!!!!!!!!!!!!!!1");
        }
    }
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }else{
            System.out.println("erro!!!!!!!!!!!!!!!1");
        }
    }

}
class HeroNode{
    int no;
    String name;
    HeroNode parent;
    HeroNode left;//左
    HeroNode right;//右
    int leftType = 0;//1表示前驱节点0表示子节点

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    int rightType = 0;//1表示后继节点0表示子节点
    HeroNode(int no,String name){
        this.no=no;
        this.name=name;
    }
    HeroNode(int no){
        this.no=no;
    }
/**
 * 删除指定节点（子节点不删除）
 */
public void del(int no){
    if(this.left!=null&&this.left.no==no){
        tool(true);
    }else if(this.right!=null&&this.right.no==no){
        tool(false);
        return;
    }//如果未找到则继续递归
    //判断当前子节点是否为null
    if(this.left!=null){
        this.left.delNode(no);
    }
    if(this.right!=null){
        this.right.delNode(no);
    }
    return;
}
private void tool(boolean b) {
    if (b) {
        //找到之后：
        //        先判断是子节点还是叶子节点
        if (this.left.isLeafNode()) {//如果是叶子节点
            this.left = null;
            return;
        } else if (this.left.isChildNode()) {//如果是子节点
            if (this.left != null && this.right == null) {//如果其删除节点只有一个子节点
                this.left = this.left.left;
            } else if (this.right != null && this.left == null) {
                this.right = this.right.right;
            } else {
                this.left.left.left = this.left.right;
                this.left = this.left.left;
            }

        }
        return;
    }//判断是否为叶子节点(无子节点的节点)
    else {
        //找到之后：
        //        先判断是子节点还是叶子节点
        if (this.right.isLeafNode()) {//如果是叶子节点
            this.right = null;
            return;
        } else if (this.right.isChildNode()) {//如果是子节点
            if (this.left != null && this.right == null) {//如果其删除节点只有一个子节点
                this.left = this.left.left;
            } else if (this.right != null && this.left == null) {//如果其删除节点只有一个子节点
                this.right = this.right.right;
            } else {//两个子节点
                this.right.left.left = this.right.right;
                this.right = this.right.left;
            }
        }
        return;
    }
}
public boolean isLeafNode(){
    return (this.right==null&&this.left==null);
}
    //判断是否为子节点
    public boolean isChildNode(){
        return (this.right!=null||this.left!=null);
    }
    /**
     * 删除指定节点及其子节点
     * 因二叉树为单项所以我们不能删除当前节点只能删除其子节点
     */
    public void delNode(int no){
        //判断当前子节点是否为空,并判断是否为寻找的元素
        if (this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }else if(this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }//如果未找到则继续递归
            //判断当前子节点是否为null
        if(this.left!=null){
          this.left.delNode(no);
        }
        if(this.right!=null){
            this.right.delNode(no);
        }
        return;
    }
    /**
     * 前序查找
     */
    public HeroNode preSearch(int no){
        if(no==this.no){
            return this;
        }
        HeroNode h=null;
        if(this.left!=null){
            h=this.left.preSearch(no);
        }
        if(h!=null){
            return h;
        }
        if(this.right!=null){
            h= this.right.preSearch(no);
        }
                return h;
    }
    /**
     * 中序查找
     */
    public HeroNode infixSearch(int no){

        HeroNode h = null;
        if(this.left!=null){
            h=left.infixSearch(no);
        }
        System.out.println(this.getNo());
        if(h!=null){
            return h;
        }
        if(no==this.no){
            return this;
        }
        if(this.right!=null){
            h=right.infixSearch(no);
        }
        return h;
    }
    /**
     * 后序查找
     */
    public HeroNode postSearch(int no){
        HeroNode h = null;
        if(this.left!=null){
            h=this.left.postSearch(no);
        }
        if(h!=null){
            return h;
        }
        if(this.right!=null){
            h=this.right.postSearch(no);
        }
        if(no==this.no){
            return this;
        }
        return h;
    }
    /**
     * 前序排序
     */
    public void preOrder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }

}

    /**
     * 中序排序
     * @return
     */
    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }

    /**
     * 后序排序
     * @return
     */
    public void postOrder(){
        if(this.left!=null){
            this.left.postOrder();
        }
        if(this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}